/*
2021-8-3
https://leetcode-cn.com/problems/count-number-of-special-subsequences/
*/
class Solution {
    const int mod=1e9+7;
public:
    int countSpecialSubsequences(vector<int>& nums) {
        int f0=0,f1=0,f2=0;
        for(auto t:nums)
        {
            if(t==0) f0=(f0*2%mod+1)%mod;
            else if(t==1) f1=(f1*2%mod+f0)%mod;
            else f2=(f2*2%mod+f1)%mod;
        }
        return f2;
    }
};
